package com.exercises;

import java.util.*;

class Exercise37 {
    public static void main(String[] args) {

        char[][] board = new char[9][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                board[i][j] = '.';
            }
        }

        board[0][0] = '5';
        board[0][1] = '3';
        board[0][4] = '7';
        board[1][0] = '6';
        board[1][3] = '1';
        board[1][4] = '9';
        board[1][5] = '5';
        board[2][1] = '9';
        board[2][2] = '8';
        board[2][7] = '6';
        board[3][0] = '8';
        board[3][4] = '6';
        board[3][8] = '3';
        board[4][0] = '4';
        board[4][3] = '8';
        board[4][5] = '3';
        board[4][8] = '1';
        board[5][0] = '7';
        board[5][4] = '2';
        board[5][8] = '6';
        board[6][1] = '6';
        board[6][6] = '2';
        board[6][7] = '8';
        board[7][3] = '4';
        board[7][4] = '1';
        board[7][5] = '9';
        board[7][8] = '5';
        board[8][4] = '8';
        board[8][7] = '7';
        board[8][8] = '9';
        new Exercise37().solveSudoku(board);


    }


    public void solveSudoku(char[][] board) {
        Map<Integer, List<Integer>> row = new HashMap<>();
        Map<Integer, List<Integer>> columns = new HashMap<>();
        Map<Integer, List<Integer>> block = new HashMap<>();
        for (int i = 1; i <= 9; i++) {
            row.put(i, new ArrayList<>());
            columns.put(i, new ArrayList<>());
            block.put(i, new ArrayList<>());
        }
        List<Integer> iList = new ArrayList<>();
        List<Integer> jList = new ArrayList<>();
        List<Integer> vList = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int blockIdx = (i / 3) * 3 + j / 3 + 1;
                if ('.' != board[i][j]) {
                    int value = Integer.parseInt(String.valueOf(board[i][j]));
                    System.out.print(value);
                    row.get(i + 1).add(Integer.valueOf(value));
                    columns.get(j + 1).add(Integer.valueOf(value));
                    block.get(blockIdx).add(Integer.valueOf(value));
                } else {
                    iList.add(i);
                    jList.add(j);
                    vList.add(0);
                    System.out.print(" ");
                }
                System.out.print(" ");

            }
            System.out.println();
        }
        for (int a = 0; a < iList.size(); ) {
            int i = iList.get(a);
            int j = jList.get(a);
            Integer v = vList.get(a) + 1;
            int blockIdx = (i / 3) * 3 + j / 3 + 1;

            if (v > 9) {
                board[i][j] = '.';
                vList.set(a, 0);
                i = iList.get(a - 1);
                j = jList.get(a - 1);
                v = vList.get(a - 1);
                blockIdx = (i / 3) * 3 + j / 3 + 1;
                row.get(i + 1).remove(Integer.valueOf(v));
                columns.get(j + 1).remove(Integer.valueOf(v));
                block.get(blockIdx).remove(Integer.valueOf(v));
                a--;
                continue;
            }


            if (row.get(i + 1).contains(v) || columns.get(j + 1).contains(v) || block.get(blockIdx).contains(v)) {
                vList.set(a, v);
                continue;
            } else {
                vList.set(a, v);
                row.get(i + 1).add(v);
                columns.get(j + 1).add(v);
                block.get(blockIdx).add(v);
                board[i][j] = v.toString().charAt(0);
                a++;
                print(board);
            }

        }
    }


    private static void print(char[][] a) {
        System.out.println("===================");
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if ('.' != a[i][j]) {
                    int value = Integer.parseInt(String.valueOf(a[i][j]));
                    System.out.print(value);
                } else {
                    System.out.print(" ");
                }
                System.out.print(" ");

            }
            System.out.println();
        }
    }
}
